import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by L.jp
 * Description:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出
 * 来的所有字符串 abc,acb,bac,bca,cab 和 cba 。
 * User: 86189
 * Date: 2021-12-26
 * Time: 15:30
 */
// 我们想要得到合适的排列组合，一定是深度优先的
//该问题可以把目标串理解成两部分：第一部分：以哪个字符开头，第二部分：剩下的是子问题
//所以，我们要让每个字符都要做一遍开头，然后在求解子问题，这里都是采用固定一个头字符，然后剩余的交换的的思想
/*对于无重复值的情况
         固定第一个字符，递归取得首位后面的各种字符串组合；
        再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；
        递归的出口，就是只剩一个字符的时候，也就是固定最后一个字符的时候，递归的循环过程，
        就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。*/
    //对于有重复的值，我们可以在对字符串全排列的过程中，定义一个去重的set,只要当前字符是没有出现的，就加入到set中
    //或者可以定义一个判断函数，然后不用set,直接用list.contains()判断，不包含那么就把当前字符串数组转换为字符串，再加入到链表中
public class MyString {
    /*
     * @param str:待排列的字符串
     * [str]
     * @return   ArrayList<String>  全排列后的字符串集合
     * @description    TODO
     */
    public static ArrayList<String> Permutation(String str) {
        if(str==null){
            return new ArrayList<>();
        }
        //结果集合
        ArrayList<String> ret=new ArrayList<>();
        //求字符串排列的结果集
        PermutationHelper(str.toCharArray(),0,ret);
        return  ret;
        //如果返回类型是String[]，那么就可以是return ret.toArray(new String[ret.size()];
    }
    //判断去重函数
    public static boolean isContains(ArrayList<String> ret,char[] chars){
        return  ret.contains(String.valueOf(chars));//用于排除bab这种情况
    }
    //字符串全排列函数
    //递归，dfs
    public static void PermutationHelper(char[] chars, int start, ArrayList<String> ret) {
        //如果当前固定的字符当立最后一个了，那么说明前面的都被固定过了，只有一种情况，那么这个字符串肯定符合情况
        if(start==chars.length-1){
            //说明这是一个符合要求的排列，将字符数组转换为字符串
            if(!isContains(ret, chars)) {
                ret.add(String.valueOf(chars));
            }
            return;
        }
        //否则需要对字符串全排列
        // for循环和swap的含义：对于“ABC”，
        // 第一次'A' 与 'A'交换(i==0)，字符串为"ABC", start为0， 相当于固定'A'
        // 第二次'A' 与 'B'交换(i==1)，字符串为"BAC", start为0， 相当于固定'B'
        // 第三次'A' 与 'C'交换(i==2)，字符串为"CBA", start为0， 相当于固定'C'
        //实际就是以固定的start字符开头，分别与i字符依次交换
        //递归，然后以start+1开头，然后交换剩下的

        //如果不用上面的判断重复函数，就可以定义一个
        //Set<Character> set=new HashSet<>()用于去重

        for(int i=start;i<chars.length;i++){
            //或者
            /*
            if(set.contains(chars[i])) continue;
            set.add(chars[i]);//排除重复字符的情况

             */
            swap(chars,start,i);
            PermutationHelper(chars,start+1,ret);
            //回溯
            // 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
            // 然后进行第三次交换，才能得到"CBA"
            swap(chars,start,i);
        }
    }
    //交换函数
    public static void swap(char[] chars,int start,int i){
        char tmp=chars[start];
        chars[start]=chars[i];
        chars[i]=tmp;
    }

    public static void main(String[] args) {
        System.out.println(Permutation("abc"));
    }
}
